#include <debug.h>
#include "threads/thread.h"
#include "threads/malloc.h"
#include "threads/vaddr.h"
#include "userprog/pagedir.h"
#include "vm/page.h"
#include "vm/frame.h"
#include "vm/swap.h"

bool free_and_false (struct page *p);

bool page_stack_growth(void *uaddr)
{
	void *upage = pg_round_down(uaddr);
	
	void *kpage = get_frame (true);
	struct thread *t = thread_current ();
	
	if(pagedir_get_page (t->pagedir, upage) != NULL 
		 || !frametable_set_frame(upage,kpage,true))
	{
		free_frame(kpage);
		return false;
	}
	return true;
}

/* Initializes the supplemental page table of thread T. */
bool pagetbl_init (struct thread *t)
{
	ASSERT (t->pagetbl == NULL);
	ASSERT (t->pagetbl_lock == NULL);

	t->pagetbl = malloc (sizeof (struct hash));
	if (t->pagetbl == NULL)
		return false;

	t->pagetbl_lock = malloc (sizeof (struct lock));
	if (t->pagetbl_lock == NULL)
	{
		free (t->pagetbl);
		return false;
	}
	lock_init (t->pagetbl_lock);

	return hash_init (t->pagetbl, page_hash, page_less, NULL);
}

/* Destroys supplemental page table of thread T. */
void pagetbl_destroy (struct thread *t)
{
	if (t == NULL)
		return;

	if (t->pagetbl != NULL && t->pagetbl_lock != NULL)
	{
		lock_acquire (t->pagetbl_lock);
		hash_destroy (t->pagetbl, page_destroy);
		lock_release (t->pagetbl_lock);

		free (t->pagetbl);
		free (t->pagetbl_lock);
	}
}

/* Inserts mapping information from UPAGE to KPAGE 
	 into page directory and supplemental page table. */
bool page_insert (void *upage, void *kpage, bool writable)
{
	ASSERT (is_user_vaddr (upage));
	ASSERT (is_kernel_vaddr (kpage));

	struct thread *cur = thread_current ();

	/* Prepare supplemental page table entry. */
	struct page *p = malloc (sizeof (struct page));
	if (p == NULL)
		return false;

	p->uaddr = upage;
	p->swap_dsk_idx = -1; /* -1 indicates that this page is not swapped out. */
	p->owner = cur;

	lock_acquire (cur->pagetbl_lock);

	struct hash_elem *elem = hash_find (cur->pagetbl, &p->hash_elem);

	/* Page info exists in the supplemental page table. */
	if (elem != NULL)
	{
		free (p);
		p = hash_entry (elem, struct page, hash_elem);

		/* This page is currently mapped. So we can't map again. */
		if (get_kpage (p) != NULL)
		{
			return false;
		}
		/* This page was mapped, but not now. */
		else
		{
			p->swap_dsk_idx = -1;
		}
	}
	/* UPAGE was never mapped. */
	else
	{
		/* Insert page info into supplemental page table. */
		struct hash_elem *old = hash_insert (cur->pagetbl, &p->hash_elem);
		if (old != NULL)
			return free_and_false (p);
	}

	/* Add a mapping in page directory from UPAGE to KPAGE. */
	if (!pagedir_set_page (cur->pagedir, upage, kpage, writable))
		return free_and_false (p);

	/* When a page is first loaded into a frame in memory, 
		 set access bit for that frame to 1 for clock algorithm. */
	pagedir_set_accessed (cur->pagedir, upage, true);

	lock_release (cur->pagetbl_lock);

	return true;
}

/* Frees page P and returns false. */
bool free_and_false (struct page *p)
{
	free (p);
	return false;
}

/* Returns the page containing the given virtual address,
	 or a null pointer if no such page exists. */
struct page *page_lookup (void *address, struct thread *t)
{
	if (is_kernel_vaddr (address))
		return NULL;

	if (t == NULL)
		t = thread_current ();

	if (t->pagetbl_lock == NULL)
		return NULL;

	lock_acquire (t->pagetbl_lock);

	struct page p;
	struct hash_elem *e;

	p.uaddr = address;
	e = hash_find (t->pagetbl, &p.hash_elem);
	lock_release (t->pagetbl_lock);

	return e != NULL ? hash_entry (e, struct page, hash_elem) : NULL;
}

/* Returns the kernel virtual address 
	 which is mapped to user virtual address of page P,
	 or a null pointer if not mapped. */
void *get_kpage (struct page *p)
{
	if (p == NULL)
		return NULL;

	return pagedir_get_page (p->owner->pagedir, p->uaddr);
}

/* Returns a hash value for page p. */
unsigned page_hash (const struct hash_elem *p_, void *aux UNUSED)
{
	const struct page *p = hash_entry (p_,struct page, hash_elem);
	return hash_bytes (&p->uaddr, sizeof p->uaddr);
}

/* Returns true if page a precedes page b. */
bool page_less (const struct hash_elem *a_, const struct hash_elem *b_, void *aux UNUSED)
{
	const struct page *a = hash_entry (a_, struct page, hash_elem);
	const struct page *b = hash_entry (b_, struct page, hash_elem);

	return a->uaddr < b->uaddr;
}

/* Destructor function for supplementabl page table. */
void page_destroy (struct hash_elem *p_, void *aux UNUSED)
{
	struct page *p = hash_entry (p_, struct page, hash_elem);

	/* Corresponding physical frame is swapped out. */
	if (p->swap_dsk_idx != -1)
		swap_clear (p);

	free (p);
}
